package offer.question1_10.solutions;

public class QSolution3_2 {

    /*
     * 不修改数组找出重复的数字
     *
     * 在一个长度为 n+1 的数组中，所有的数字都在 1~n 范围内，所以数组中肯定有一个数字是重复的。请找出这个数字
     *
     * 假设 1~n 的中点为 m，那么把原数组分为两部分：1~m，m+1~n，如果原数组中值在 1~m 这个范围内的元素个数大于 m 个，那么在这一半
     * 的区间中肯定存在重复元素，否则 m+1~n 这个区间中包含重复元素。然后继续把包含重复元素的区间一分为二，直到找到重复元素。
     *
     * 以数组 [2, 1, 5, 2, 4, 6, 6, 7] 为例，1~7 分为两个区间，1~4 为前半部分，而 5~7 为后半部分。[1-4] 出现了 4 次，[5-7]
     * 出现了 4 次，那么就说明后一个区间中包含重复元素，因此把 [5-7] 继续细分为 [5-6] 和 [7-7] 两个部分。这时，由于 [5-6] 部分只有
     * 两个元素，因此，直接到数组中去查找 5 和 6 分别出现的次数，如果超过 1 次，就说明是重复元素
     */

}
